package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/3/13 17:48
 * @description <p>字母异位词分组</p>
 */

import java.util.*;

/**
 * 题目：给定一组单词，请将它们按照变位词分组。例如，输入一组单
 * 词["eat", "tea", "tan", "ate", "nat", "bat"]，这组单词可以分成 3 组，分别是["eat",
 * "tea", "ate"]、["tan", "nat"]和["bat"]。假设单词中只包含英文小写字母。
 */
public class toOffer5_3_33 {
    public static void main(String[] args) {
        String[] strs = {""};
        List<List<String>> lists = groupAnagrams(strs);
        for (int i = 0; i < lists.size(); i++) {
            for (String s : lists.get(i)) {
                System.out.print(s + " ");
            }
            System.out.println();
        }
    }

    /**
     * 思路：
     *  对string数组里的每个string做排序，排序后相同就说明它们是同一组变位词
     *
     * @param strs
     * @return
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String newStr = new String(chars);
            //用一个map装数据，k是排好序的string数据、value是需要往里添加string数据的list集合
            //map里面没有newStr就直接添加新的list集合，有就往已经存在的集合里加原未排序的string数据
            map.putIfAbsent(newStr, new ArrayList<>());
            map.get(newStr).add(str);
        }

        return new ArrayList<>(map.values());
    }
}
